<!DOCTYPE html>


  <html class="dark page-post">


<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  
  <title>7种常用的排序算法总结 | Poetry&#39;s Blog</title>

  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

  
    <meta name="keywords" content="排序算法,">
  

  <meta name="description" content="排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。">
<meta name="keywords" content="排序算法">
<meta property="og:type" content="article">
<meta property="og:title" content="7种常用的排序算法总结">
<meta property="og:url" content="http://blog.poetries.top/2016/04/30/排序算法总结/index.html">
<meta property="og:site_name" content="Poetry&#39;s Blog">
<meta property="og:description" content="排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://images.cnitblog.com/blog/441348/201301/18154959-d81ff153bc6647e49d6296303d6e6484.jpg">
<meta property="og:image" content="http://images.cnitblog.com/blog/441348/201301/18160646-f229ab053232408fbf80b9f2d1737e28.jpg">
<meta property="og:image" content="https://segmentfault.com/img/bVq1vH">
<meta property="og:updated_time" content="2020-08-15T04:25:31.942Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="7种常用的排序算法总结">
<meta name="twitter:description" content="排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。">
<meta name="twitter:image" content="http://images.cnitblog.com/blog/441348/201301/18154959-d81ff153bc6647e49d6296303d6e6484.jpg">

  

  
    <link rel="icon" href="/favicon.ico">
  

  <link href="/css/styles.css?v=c114cbeddx" rel="stylesheet">
<link href="/css/other.css?v=c114cbeddx" rel="stylesheet">


  
    <link rel="stylesheet" href="/css/personal-style.css">
  

  

  
  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "//hm.baidu.com/hm.js?40b1f89aa80f2527b3db779c6898c879";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>


  
  <script type="text/javascript">
	(function(){
	    var bp = document.createElement('script');
	    var curProtocol = window.location.protocol.split(':')[0];
	    if (curProtocol === 'https') {
	        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
	    }
	    else {
	        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
	    }
	    var s = document.getElementsByTagName("script")[0];
	    s.parentNode.insertBefore(bp, s);
	})();
  </script>



  
    <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.3.0/css/font-awesome.min.css">
  

  <!-- 聊天系统 -->
  
    
   <link type="text/css" rel="stylesheet" href="/renxi/default.css">
   <style>
      #modal {
        position: static !important;
      }
      .filter {
        width: 100%;
        height: 100%;
        position: absolute;
        top: 0;
        left: 0;
        background: #fe5757;
        animation: colorChange 30s ease-in-out infinite;
        animation-fill-mode: both;
        mix-blend-mode: overlay;
      }
  
      @keyframes colorChange {
        0%, 100% {
            opacity: 0;
        }
        50% {
            opacity: .9;
        }
      }
   </style>
</head>
</html>
<body>
  
  
    <span id="toolbox-mobile" class="toolbox-mobile">导航</span>
  

  <div class="post-header CENTER">
   
  <div class="toolbox">
    <a class="toolbox-entry" href="/">
      <span class="toolbox-entry-text">导航</span>
      <i class="icon-angle-down"></i>
      <i class="icon-home"></i>
    </a>
    <ul class="list-toolbox">
      
        <li class="item-toolbox">
          <a
            class="CIRCLE"
            href="/archives/"
            rel="noopener noreferrer"
            target="_self"
            >
            博客
          </a>
        </li>
      
        <li class="item-toolbox">
          <a
            class="CIRCLE"
            href="/categories/"
            rel="noopener noreferrer"
            target="_self"
            >
            分类
          </a>
        </li>
      
        <li class="item-toolbox">
          <a
            class="CIRCLE"
            href="/tags/"
            rel="noopener noreferrer"
            target="_self"
            >
            标签
          </a>
        </li>
      
        <li class="item-toolbox">
          <a
            class="CIRCLE"
            href="/search/"
            rel="noopener noreferrer"
            target="_self"
            >
            搜索
          </a>
        </li>
      
        <li class="item-toolbox">
          <a
            class="CIRCLE"
            href="/link/"
            rel="noopener noreferrer"
            target="_self"
            >
            友链
          </a>
        </li>
      
        <li class="item-toolbox">
          <a
            class="CIRCLE"
            href="/about/"
            rel="noopener noreferrer"
            target="_self"
            >
            关于
          </a>
        </li>
      
    </ul>
  </div>


</div>


  <div id="toc" class="toc-article">
    <strong class="toc-title">文章目录<i class="iconfont toc-title" style="display:inline-block;color:#87998d;width:20px;height:20px;">&#xf004b;</i></strong>
    <ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-冒泡排序"><span class="toc-text">1-冒泡排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-选择排序"><span class="toc-text">2-选择排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-快速排序"><span class="toc-text">3-快速排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-插入排序"><span class="toc-text">4-插入排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-希尔排序"><span class="toc-text">5-希尔排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-归并排序"><span class="toc-text">6-归并排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#7-堆排序"><span class="toc-text">7-堆排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#总结"><span class="toc-text">总结</span></a></li></ol>
  </div>
  




<div class="content content-post CENTER">
   <!-- canvas 彩带 -->
<canvas id="evanyou" width="1302" height="678" style="position: fixed;width: 100%;height: 100%;top: 0;left:0;z-index:-1;"></canvas>

<article id="post-排序算法总结" class="article article-type-post" itemprop="blogPost">
  <header class="article-header" style="position:relative;">
    <h1 class="post-title">7种常用的排序算法总结</h1>

    <div class="article-meta">
      <span>
        <i class="icon-calendar"></i>
        <span>2016.04.30</span>
      </span>

      
        <span class="article-author">
          <i class="icon-user"></i>
          <span>Poetry</span>
        </span>
      

      
  <span class="article-category">
    <i class="icon-list"></i>
    <a class="article-category-link" href="/categories/Algorithm/">Algorithm</a>
  </span>



      

      
      <i class="fa fa-eye"></i> 
        <span id="busuanzi_container_page_pv">
           &nbsp热度 <span id="busuanzi_value_page_pv">
           <i class="fa fa-spinner fa-spin"></i></span>℃
        </span>
      
      
       
          <span class="post-count">
            <i class="fa fa-file-word-o"></i>&nbsp
            <span>字数统计 4.1k字</span>
          </span>

          <span class="post-count">
            <i class="fa fa-columns"></i>&nbsp
            <span>阅读时长 16分</span>
          </span>
      
      
    </div>

    <i class="iconfont" id="toc-eye" style="display:inline-block;color:#b36619;position:absolute;top:0;right:0;cursor:pointer;
    font-size: 24px;">&#xe61c;</i>

  </header>

  <div class="article-content">
    
      <div id="container">
        <p><strong>排序算法</strong>：一种能将一串数据依照特定的排序方式进行排列的一种算法。<br><strong>排序算法性能</strong>：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。<br><strong>稳定性</strong>：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。<br><a id="more"></a></p>
<hr>
<h3 id="1-冒泡排序"><a href="#1-冒泡排序" class="headerlink" title="1-冒泡排序"></a><strong>1-冒泡排序</strong></h3><p><strong>原理</strong><br>俩俩比较相邻记录的排序码，若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。冒泡法大家都较熟悉。其原理为从a[0]开始，依次将其和后面的元素比较,若a[0]&gt;a[i]，则交换它们，一直比较到a[n]。同理对a<a href="http://images.cnitblog.com/blog/441348/201301/18154959-d81ff153bc6647e49d6296303d6e6484.jpg" target="_blank" rel="noopener">1</a>,a<a href="http://images.cnitblog.com/blog/441348/201301/18160646-f229ab053232408fbf80b9f2d1737e28.jpg" target="_blank" rel="noopener">2</a>,…a[n-1]处理，即完成排序</p>
<p><strong>冒泡排序的基本概念：</strong></p>
<p>依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。</p>
<p><strong>实现：</strong></p>
<p>外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环依次重复9，8，…，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,…,9，对于每一个i,j的值依次为1,2,…10-i。</p>
<p>图示：<br><img src="http://images.cnitblog.com/blog/441348/201301/18154959-d81ff153bc6647e49d6296303d6e6484.jpg" alt="此处输入图片的描述"></p>
<p><strong>性能</strong><br>时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。</p>
<p><strong>优化</strong><br>若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变</p>
<p><strong>代码</strong></p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">#include&lt;stdio.h&gt;</span><br><span class="line">void sort(int *a,int len)</span><br><span class="line">&#123;</span><br><span class="line">    int i,j,t;</span><br><span class="line">    </span><br><span class="line">    for( i = 0;i&lt;len-1;++i)</span><br><span class="line">    &#123;</span><br><span class="line">        for(j = 0;j&lt;len-1-i;++j) 或者 j=i+1;j&lt;len;++j</span><br><span class="line">        &#123;</span><br><span class="line">            if(a[j] &gt;a[j+1])</span><br><span class="line">            &#123;</span><br><span class="line">                t  = a[j];</span><br><span class="line">                a[j] = a[j+1];</span><br><span class="line">                a[j+1] = t;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">        </span><br><span class="line">&#125;</span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">    int a[6] = &#123;10,2,8,-8,11,0&#125;;</span><br><span class="line">    int i = 0;</span><br><span class="line">    sort(a,6);</span><br><span class="line">    </span><br><span class="line">    for(i = 0; i&lt;6;++i)</span><br><span class="line">    &#123;</span><br><span class="line">        printf(&quot;%d &quot;,a[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;\n&quot;);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>冒泡法原理简单，但其缺点是交换次数多，效率低。下面介绍一种源自冒泡法但更有效率的方法“选择法”。</p>
<hr>
<h3 id="2-选择排序"><a href="#2-选择排序" class="headerlink" title="2-选择排序"></a><strong>2-选择排序</strong></h3><p><strong>原理</strong><br>每次从未排序的序列中找到最小值，记录并最后存放到已排序序列的末尾.选择法循环过程与冒泡法一致，它还定义了记号k=i,然后依次把a[k]同后面元素比较，若a[k]&gt;a[j],则使k=j.最后看看k=i是否还成立，不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换，提高了效率。</p>
<p><strong>性能</strong><br>时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的（把最小值交换到已排序的末尾导致的），每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。</p>
<p><strong>代码</strong><br><figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">//直接选择排序</span><br><span class="line"></span><br><span class="line">#include&lt;stdio.h&gt;</span><br><span class="line"></span><br><span class="line">void sort(int *a,int len)</span><br><span class="line">&#123;</span><br><span class="line">	int i,j,min,t;</span><br><span class="line"></span><br><span class="line">	for(i = 0;i&lt;len-1;++i)</span><br><span class="line">	&#123;</span><br><span class="line">		for(min=i,j=i+1;j&lt;len;++j)</span><br><span class="line">		&#123;</span><br><span class="line">			if(a[min]&gt;a[j])</span><br><span class="line">				min = j;</span><br><span class="line"></span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		if(min!=i)</span><br><span class="line">		&#123;</span><br><span class="line">			t = a[i];</span><br><span class="line">			a[i] = a[min];</span><br><span class="line">			a[min] = t;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">	int a[6] = &#123;4,0,3,2,5,1&#125;;</span><br><span class="line"></span><br><span class="line">	sort(a,6);//a代表数组的首地址</span><br><span class="line"></span><br><span class="line">	for(int i=0;i&lt;6;++i)</span><br><span class="line">		printf(&quot;%d\n&quot;,a[i]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>选择法比冒泡法效率更高，但说到高效率，非“快速法”莫属，现在就让我们来了解它。 </p>
<hr>
<h3 id="3-快速排序"><a href="#3-快速排序" class="headerlink" title="3-快速排序"></a><strong>3-快速排序</strong></h3><p><strong>原理</strong><br>基本思想：</p>
<p>快速排序是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。</p>
<p><strong>实现：</strong><br>设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。</p>
<p><strong>一趟快速排序的算法是：</strong><br>1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；<br>2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；<br>3）从j开始向前搜索，即由后开始向前搜索（j – ），找到第一个小于key的值A[j]，A[i]与A[j]交换；<br>4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换；<br>5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）</p>
<p>图示：<br><img src="http://images.cnitblog.com/blog/441348/201301/18160646-f229ab053232408fbf80b9f2d1737e28.jpg" alt="此处输入图片的描述"></p>
<p><strong>举例说明：</strong></p>
<p>如无序数组[6 2 4 1 5 9]</p>
<ul>
<li><p>a),先把第一项[6]取出来,</p>
<ul>
<li><p>用[6]依次与其余项进行比较,</p>
</li>
<li><p>如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边</p>
</li>
<li><p>如果比[6]大就放[6]后边,9比[6]大,放到[6]后边,//6出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气十足~</p>
</li>
</ul>
</li>
</ul>
<p><strong>一趟排完后变成下边这样:</strong></p>
<ul>
<li><p>排序前 6 2 4 1 5 9</p>
</li>
<li><p>排序后 2 4 1 5 6 9</p>
</li>
</ul>
<p>b),对前半拉[2 4 1 5]继续进行快速排序</p>
<p><strong>重复步骤a)后变成下边这样:</strong></p>
<ul>
<li><p>排序前 2 4 1 5</p>
</li>
<li><p>排序后 1 2 4 5</p>
</li>
</ul>
<p><strong>前半拉排序完成,总的排序也完成:</strong></p>
<ul>
<li><p>排序前:[6 2 4 1 5 9]</p>
</li>
<li><p>排序后:[1 2 4 5 6 9]</p>
</li>
</ul>
<p><strong>性能</strong><br>快排的平均时间复杂度为O(NlogN），空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N)；且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。</p>
<p>优化<br>当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。<br>所以快排的优化思路如下：</p>
<p>优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序；或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。<br>在规模较小情况下，采用直接插入排序<br>代码</p>
<hr>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">//快速排序</span><br><span class="line"></span><br><span class="line">#include&lt;stdio.h&gt;</span><br><span class="line"></span><br><span class="line">int FindPos(int * a, int low, int high)</span><br><span class="line">&#123;</span><br><span class="line">	int val = a[low];</span><br><span class="line"></span><br><span class="line">	while (low &lt; high)</span><br><span class="line">	&#123;</span><br><span class="line">		while (low&lt;high  &amp;&amp; a[high]&gt;=val)</span><br><span class="line">			--high;</span><br><span class="line">		a[low] = a[high];</span><br><span class="line"></span><br><span class="line">		while (low&lt;high &amp;&amp; a[low]&lt;=val)</span><br><span class="line">			++low;</span><br><span class="line">		a[high] = a[low];</span><br><span class="line">	&#125;//终止while循环之后low和high一定是相等的</span><br><span class="line"></span><br><span class="line">	a[low] = val; </span><br><span class="line"></span><br><span class="line">	return high; //high可以改为low, 但不能改为val 也不能改为a[low]  也不能改为a[high]</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void QuickSort(int *a,int low,int high)</span><br><span class="line">&#123;</span><br><span class="line">	int pos;</span><br><span class="line"></span><br><span class="line">	if(low&lt;high)</span><br><span class="line">	&#123;</span><br><span class="line">		pos = FindPos(a,low,high);//找到a数组下标low-high  </span><br><span class="line">		QuickSort(a,low,pos-1);//把元素劈成两半  左半边</span><br><span class="line">		QuickSort(a,pos+1,high);//右半边</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">	int i;</span><br><span class="line">	int a[6] = &#123;2,1,3,0,5,4&#125;;</span><br><span class="line"></span><br><span class="line">	QuickSort(a,0,5);//0表示第一个元素下标 5表示最后一个元素的下标</span><br><span class="line">	</span><br><span class="line">	for(i = 0;i&lt;6;++i)</span><br><span class="line">		printf(&quot;%d\n&quot;,a[i]);</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="4-插入排序"><a href="#4-插入排序" class="headerlink" title="4-插入排序"></a><strong>4-插入排序</strong></h3><p><strong>原理</strong><br>依次选择一个待排序的数据，插入到前边已排好序的序列中。</p>
<p><strong>性能</strong><br>时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。</p>
<p><strong>优化</strong><br>直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。<br>折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。</p>
<p><strong>使用场景</strong><br>当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率</p>
<p><strong>代码：</strong></p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">void insert_sort(int *a,int n) </span><br><span class="line"></span><br><span class="line">&#123; </span><br><span class="line">    </span><br><span class="line">    int i,j,temp; </span><br><span class="line">    </span><br><span class="line">    for(i=1;i&lt;n;i++) </span><br><span class="line">    &#123; </span><br><span class="line">    </span><br><span class="line">        temp=a[i]; /*temp为要插入的元素*/ </span><br><span class="line">        </span><br><span class="line">        j=i-1; </span><br><span class="line">        </span><br><span class="line">        while(j&gt;=0&amp;&amp;temp&lt;a[j]) </span><br><span class="line">        &#123; </span><br><span class="line">            /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/ </span><br><span class="line">            </span><br><span class="line">            a[j+1]=a[j]; </span><br><span class="line">            </span><br><span class="line">            j--; </span><br><span class="line">    </span><br><span class="line">        &#125; </span><br><span class="line">    </span><br><span class="line">         a[j+1]=temp; /*插入*/ </span><br><span class="line">    </span><br><span class="line">    &#125; </span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="5-希尔排序"><a href="#5-希尔排序" class="headerlink" title="5-希尔排序"></a><strong>5-希尔排序</strong></h3><p><strong>原理</strong></p>
<p>Shell法是一个叫 shell 的美国人与1969年发明的。它首先把相距k(k&gt;=1)的那几个元素排好序，再缩小k值（一般取其一半），再排序，直到k=1时完成排序</p>
<p>插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：</p>
<ul>
<li>插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。</li>
<li>但插入排序在每次往前插入时只能将数据移动一位，效率比较低。</li>
</ul>
<p><strong>性能</strong><br>开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">void shell_sort(int *a,int n) </span><br><span class="line"></span><br><span class="line">&#123; </span><br><span class="line"></span><br><span class="line">    int i,j,k,x; </span><br><span class="line">    </span><br><span class="line">    k=n/2; /*间距值*/ </span><br><span class="line">    </span><br><span class="line">    while(k&gt;=1) </span><br><span class="line">    &#123; </span><br><span class="line">    </span><br><span class="line">        for(i=k;i&lt;n;i++)</span><br><span class="line">        &#123; </span><br><span class="line">        </span><br><span class="line">                x=a[i]; </span><br><span class="line">                </span><br><span class="line">                j=i-k; </span><br><span class="line">                </span><br><span class="line">                while(j&gt;=0&amp;&amp;x&lt;a[j]) </span><br><span class="line">                &#123; </span><br><span class="line">                    </span><br><span class="line">                    a[j+k]=a[j]; </span><br><span class="line">                    </span><br><span class="line">                    j-=k; </span><br><span class="line">                &#125; </span><br><span class="line">                </span><br><span class="line">                   a[j+k]=x;    </span><br><span class="line">                </span><br><span class="line">        &#125; </span><br><span class="line">                </span><br><span class="line">                k/=2; /*缩小间距值*/ </span><br><span class="line">        </span><br><span class="line">    &#125; </span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="6-归并排序"><a href="#6-归并排序" class="headerlink" title="6-归并排序"></a><strong>6-归并排序</strong></h3><p><strong>原理</strong></p>
<p><strong>分而治之思想：</strong></p>
<ul>
<li>Divide：将n个元素平均划分为各含n/2个元素的子序列；</li>
<li>Conquer：递归的解决俩个规模为n/2的子问题；</li>
<li>Combine：合并俩个已排序的子序列。</li>
</ul>
<p><strong>性能</strong><br>时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。</p>
<p><strong>优化</strong><br><strong>优化思路：</strong></p>
<ul>
<li>在规模较小时，合并排序可采用直接插入；</li>
<li>在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完</li>
</ul>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">//归并排序</span><br><span class="line">void merge(int arr[],int temp_arr[],int left,int mid, int right)&#123;</span><br><span class="line">    //简单归并：先复制到temp_arr，再进行归并</span><br><span class="line">    for (int i = left; i &lt;= right; i++)&#123;</span><br><span class="line">        temp_arr[i] = arr[i];</span><br><span class="line">    &#125;</span><br><span class="line">    int pa = left, pb = mid + 1;</span><br><span class="line">    int index = left;</span><br><span class="line">    while (pa &lt;= mid &amp;&amp; pb &lt;= right)&#123;</span><br><span class="line">        if (temp_arr[pa] &lt;= temp_arr[pb])&#123;</span><br><span class="line">            arr[index++] = temp_arr[pa++];</span><br><span class="line">        &#125;</span><br><span class="line">        else&#123;</span><br><span class="line">            arr[index++] = temp_arr[pb++];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while(pa &lt;= mid)&#123;</span><br><span class="line">        arr[index++] = temp_arr[pa++];</span><br><span class="line">    &#125;</span><br><span class="line">    while (pb &lt;= right)&#123;</span><br><span class="line">        arr[index++] = temp_arr[pb++];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void merge_improve(int arr[], int temp_arr[], int left, int mid, int right)&#123;</span><br><span class="line">    //优化归并：复制时，俩头小，中间大，一次比较完</span><br><span class="line">    for (int i = left; i &lt;= mid; i++)&#123;</span><br><span class="line">        temp_arr[i] = arr[i];</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = mid + 1; i &lt;= right; i++)&#123;</span><br><span class="line">        temp_arr[i] = arr[right + mid + 1 - i];</span><br><span class="line">    &#125;</span><br><span class="line">    int pa = left, pb = right, p = left;</span><br><span class="line">    while (p &lt;= right)&#123;</span><br><span class="line">        if (temp_arr[pa] &lt;= temp_arr[pb])&#123;</span><br><span class="line">            arr[p++] = temp_arr[pa++];</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            arr[p++] = temp_arr[pb--];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void merge_sort(int arr[],int temp_arr[], int left, int right)&#123;</span><br><span class="line">    if (left &lt; right)&#123;</span><br><span class="line">        int mid = (left + right) / 2;</span><br><span class="line">        merge_sort(arr,temp_arr,0, mid);</span><br><span class="line">        merge_sort(arr, temp_arr,mid + 1, right);</span><br><span class="line">        merge(arr,temp_arr,left,mid,right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void merge_sort(int arr[], int len)&#123;</span><br><span class="line">    int *temp_arr = (int*)malloc(sizeof(int)*len);</span><br><span class="line">    merge_sort(arr,temp_arr, 0, len - 1);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="7-堆排序"><a href="#7-堆排序" class="headerlink" title="7-堆排序"></a><strong>7-堆排序</strong></h3><p><strong>原理</strong></p>
<p><strong>堆的性质：</strong></p>
<ul>
<li>是一棵完全二叉树</li>
<li>每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。</li>
</ul>
<p><strong>堆排序思想：</strong></p>
<ul>
<li>将待排序的序列构造成一个最大堆，此时序列的最大值为根节点</li>
<li>依次将根节点与待排序序列的最后一个元素交换</li>
<li>再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列</li>
</ul>
<p><strong>性能</strong><br>时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。</p>
<p><strong>使用场景</strong><br>想知道最大值或最小值时，比如优先级队列，作业调度等场景。</p>
<p><strong>代码</strong></p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">/**</span><br><span class="line">     * 将数组arr构建大根堆</span><br><span class="line">     * @param arr 待调整的数组</span><br><span class="line">     * @param i   待调整的数组元素的下标</span><br><span class="line">     * @param len 数组的长度</span><br><span class="line">     */</span><br><span class="line">    void heap_adjust(int arr[], int i, int len)</span><br><span class="line">    &#123;</span><br><span class="line">        int child;</span><br><span class="line">        int temp;</span><br><span class="line">    </span><br><span class="line">        for (; 2 * i + 1 &lt; len; i = child)</span><br><span class="line">        &#123;</span><br><span class="line">            child = 2 * i + 1;  // 子结点的位置 = 2 * 父结点的位置 + 1</span><br><span class="line">            // 得到子结点中键值较大的结点</span><br><span class="line">            if (child &lt; len - 1 &amp;&amp; arr[child + 1] &gt; arr[child])</span><br><span class="line">                child ++;</span><br><span class="line">            // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点</span><br><span class="line">            if (arr[i] &lt; arr[child])</span><br><span class="line">            &#123;</span><br><span class="line">                temp = arr[i];</span><br><span class="line">                arr[i] = arr[child];</span><br><span class="line">                arr[child] = temp;</span><br><span class="line">            &#125;</span><br><span class="line">            else</span><br><span class="line">                break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    /**</span><br><span class="line">     * 堆排序算法</span><br><span class="line">     */</span><br><span class="line">    void heap_sort(int arr[], int len)</span><br><span class="line">    &#123;</span><br><span class="line">        int i;</span><br><span class="line">        // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素</span><br><span class="line">        for (int i = len / 2 - 1; i &gt;= 0; i--)</span><br><span class="line">        &#123;</span><br><span class="line">            heap_adjust(arr, i, len);</span><br><span class="line">        &#125;</span><br><span class="line">    </span><br><span class="line">        for (i = len - 1; i &gt; 0; i--)</span><br><span class="line">        &#123;</span><br><span class="line">            // 将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的</span><br><span class="line">            int temp = arr[0];</span><br><span class="line">            arr[0] = arr[i];</span><br><span class="line">            arr[i] = temp;</span><br><span class="line">            // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值</span><br><span class="line">            heap_adjust(arr, 0, i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<hr>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a><strong>总结</strong></h3><p><img src="https://segmentfault.com/img/bVq1vH" alt="此处输入图片的描述"></p>
<hr>

      </div>
    
  </div>

</article>

<button class="assist-btn2 circle" id="assist_btn2" title="点亮屏幕" style="left: 27px; top: 152px;">
  <i class="iconfont" style="display:inline-block;color:red;width:20px;height:20px;">&#xe61d;</i>
</button>
<button class="assist-btn1 circle" id="assist_btn1" title="关闭屏幕亮度" style="left: 27px; top: 152px;">
  <i class="iconfont toc-title" style="display:inline-block;color:red;width:20px;height:20px;">&#xe61d;</i>
</button>


<script src="//cdn.bootcss.com/jquery/3.1.1/jquery.min.js"></script>	

<script src="https://my.openwrite.cn/js/readmore.js" type="text/javascript"></script>
<script>
  const btw = new BTWPlugin();
  btw.init({
    id: "container",
    blogId: "22699-1592137983091-414",
    name: "前端进阶之旅",
    qrcode: "https://poetries1.gitee.io/img-repo/2020/06/qrcode.jpg",
    keyword: "3a3b3c",
  });
</script>

<script type="text/javascript">

// white theme
var body = {color: "#555", background: "#000"};
var a_tag = {color: "#222"};
var header = { background: "#222"};
var logo_line_i = {background: "#222"};
// var post_code = {background: "#eee", color: "#222"};

function switch_theme() {
 $("body").css(body);
 $("a:not('.links-of-author-item a, .site-state-item a, .site-state-posts a, .feed-link a, .motion-element a, .post-tags a, .show-commit-cls a, #donate_board a')").css(a_tag);
 $(".header, .footer").css(header);
 $(".logo-line-before i, .logo-line-after i").css(logo_line_i);
 //$(".post code").css(post_code);
 $("#idhyt-surprise-ball #idhyt-surprise-ball-animation .drag").css(a_tag);
 $(".post-title-link, .posts-expand .post-meta, .post-comments-count, .disqus-comment-count, .post-category a, .post-nav-next a, .post-nav-item a").css(a_tag);
 
 // $("code").css({color: '#c5c8c6', background: '#1d1f21'});
 //$("#assist_btn1").hide(1500);
}

$(function () {
$("#assist_btn2").css("display","none");
 $("#assist_btn1").click(function() {
     switch_theme();
$("div#toc.toc-article").css({
 "background":"#eaeaea",
 "opacity":1
});
$(".toc-article ol").show();
$("#toc.toc-article .toc-title").css("color","#a98602");
$("#assist_btn1").css("display","none");
$("#assist_btn2").css("display","block");
 });
$("#assist_btn2").click(function() {
$("#assist_btn2").css("display","none");
$("#assist_btn1").css("display","block");
$("body").css("background","url(http://www.miaov.com/static/ie/images/news/bg.png)")
     $(".header, .footer").css("background","url(http://www.miaov.com/static/ie/images/news/bg.png)")
$(".toc-article ol").toggle(1000);
 });
});


//背景随机

var Y, O, E, L, B, C, T, z, N, S, A, I;
!function() {
var e = function() {
for (O.clearRect(0, 0, L, B), T = [{
x: 0,
y: .7 * B + C
}, {
x: 0,
y: .7 * B - C
}]; T[1].x < L + C;) t(T[0], T[1])
}, t = function(e, t) {
O.beginPath(), O.moveTo(e.x, e.y), O.lineTo(t.x, t.y);
var n = t.x + (2 * I() - .25) * C,
 r = a(t.y);
O.lineTo(n, r), O.closePath(), N -= S / -50, O.fillStyle = "#" + (127 * A(N) + 128 << 16 | 127 * A(N + S / 3) + 128 << 8 | 127 * A(N + S / 3 * 2) + 128).toString(16), O.fill(), T[0] = T[1], T[1] = {
 x: n,
 y: r
}
}, a = function n(e) {
var t = e + (2 * I() - 1.1) * C;
return t > B || t < 0 ? n(e) : t
};
Y = document.getElementById("evanyou"), O = Y.getContext("2d"), E = window.devicePixelRatio || 1, L = window.innerWidth, B = window.innerHeight, C = 90, z = Math, N = 0, S = 2 * z.PI, A = z.cos, I = z.random, Y.width = L * E, Y.height = B * E, O.scale(E, E), O.globalAlpha = .6, document.onclick = e, document.ontouchstart = e, e()
}()

   
$("#toc-eye").click(function(){
$("#toc.toc-article").toggle(1000);
});

</script>


   
  <div class="text-center donation">
    <div class="inner-donation">
      <span class="btn-donation">支持一下</span>
      <div class="donation-body">
        <div class="tip text-center">扫一扫，支持poetries</div>
        <ul>
        
          <li class="item">
            
              <span>微信扫一扫</span>
            
            <img src="/images/weixin.jpg" alt="">
          </li>
        
          <li class="item">
            
              <span>支付宝扫一扫</span>
            
            <img src="/images/zhifubao.jpg" alt="">
          </li>
        
        </ul>
      </div>
    </div>
  </div>


   
  <div class="box-prev-next clearfix">
    <a class="show pull-left" href="/2016/04/17/73条日常Linux-shell命令汇总/">
        <i class="icon icon-angle-left"></i>
    </a>
    <a class="show pull-right" href="/2016/05/17/SqlServer2005学习总结/">
        <i class="icon icon-angle-right"></i>
    </a>
  </div>




</div>


  <a id="backTop" class="back-top">
    <i class="icon-angle-up"></i>
  </a>




  <div class="modal" id="modal">
  <span id="cover" class="cover hide"></span>
  <div id="modal-dialog" class="modal-dialog hide-dialog">
    <div class="modal-header">
      <span id="close" class="btn-close">关闭</span>
    </div>
    <hr>
    <div class="modal-body">
      <ul class="list-toolbox">
        
          <li class="item-toolbox">
            <a
              class="CIRCLE"
              href="/archives/"
              rel="noopener noreferrer"
              target="_self"
              >
              博客
            </a>
          </li>
        
          <li class="item-toolbox">
            <a
              class="CIRCLE"
              href="/categories/"
              rel="noopener noreferrer"
              target="_self"
              >
              分类
            </a>
          </li>
        
          <li class="item-toolbox">
            <a
              class="CIRCLE"
              href="/tags/"
              rel="noopener noreferrer"
              target="_self"
              >
              标签
            </a>
          </li>
        
          <li class="item-toolbox">
            <a
              class="CIRCLE"
              href="/search/"
              rel="noopener noreferrer"
              target="_self"
              >
              搜索
            </a>
          </li>
        
          <li class="item-toolbox">
            <a
              class="CIRCLE"
              href="/link/"
              rel="noopener noreferrer"
              target="_self"
              >
              友链
            </a>
          </li>
        
          <li class="item-toolbox">
            <a
              class="CIRCLE"
              href="/about/"
              rel="noopener noreferrer"
              target="_self"
              >
              关于
            </a>
          </li>
        
      </ul>

    </div>
  </div>
</div>



  
      <div class="fexo-comments comments-post">
    

    

    
    

    

    
    

    

<!-- Gitalk评论插件通用代码 -->
<div id="gitalk-container"></div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">
<script src="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>
<script>
const gitalk = new Gitalk({
  clientID: '5567a2c4abb858009d96',
  clientSecret: 'b9039ec056cf5c2346b3cdb63308a28c163f91e5',
  repo: 'poetries.github.io',
  owner: 'poetries',
  // 在这里设置一下截取前50个字符串, 这是因为 github 对 label 的长度有了要求, 如果超过
  // 50个字符串则会报错.
  // id: location.pathname.split('/').pop().substring(0, 49),
  id: location.pathname,
  admin: ['poetries'],
  // facebook-like distraction free mode
  distractionFreeMode: false
})
gitalk.render('gitalk-container')
</script>
<!-- Gitalk代码结束 -->



  </div>

  

  <script type="text/javascript">
  function loadScript(url, callback) {
    var script = document.createElement('script')
    script.type = 'text/javascript';

    if (script.readyState) { //IE
      script.onreadystatechange = function() {
        if (script.readyState == 'loaded' ||
          script.readyState == 'complete') {
          script.onreadystatechange = null;
          callback();
        }
      };
    } else { //Others
      script.onload = function() {
        callback();
      };
    }

    script.src = url;
    document.getElementsByTagName('head')[0].appendChild(script);
  }

  window.onload = function() {
    loadScript('/js/bundle.js?235683', function() {
      // load success
    });
  }
</script>


  <!-- 页面点击小红心 -->
  <script type="text/javascript" src="/js/clicklove.js"></script>
 
  
</body>
</html>
